#include <iostream>
#include <vector>
using namespace std;

// 非记忆化：时间复杂度O(N!)--全排列  空间复杂度O(N)--递归栈空间
// 记忆化：时间复杂度O(N^3)--共有N^2个区间，每个区间N种可能值  空间复杂度O(N^2)--额外的memo数组
// 动态规划：
class backtracking {
    int **memo;
public:
    int maxCoins(vector<int>& nums) {
        int n = nums.size();
        vector<int> points(n + 2);
        points[0] = points[n + 1] = 1;
        for (int i = 0; i < n; i++)
            points[i + 1] = nums[i];

        n += 2;
        memo = new int *[n];
        for (int i = 0; i < n; i++)
            memo[i] = new int[n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++)
                memo[i][j] = 0;
        }

        return backtrack(points, 0, n - 1);
    }

    // 每次回溯在(i, j)中返回最大coins值
    int backtrack(vector<int>& nums, int i, int j) {
        if (memo[i][j] != 0)
            return memo[i][j];
        
        // 每次从(i, j)中取第k个气球，然后计算相关值
        for (int k = i + 1; k < j; k++)
        // 这里需要与nums[i] * nums[k] * nums[j]比较，因为对于第k个数，此时只存在i和j两个气球与k相邻
            memo[i][j] = max(memo[i][j], backtrack(nums, i, k) + nums[i] * nums[k] * nums[j] + backtrack(nums, k, j));

        return memo[i][j];
    }
};


class dynamicProgram {
public:
    int maxCoins(vector<int>& nums) {
        int n = nums.size();
        int points[n + 2];
        points[0] = points[n + 1] = 1;
        for (int i = 0; i < n; i++)
            points[i + 1] = nums[i];

        n += 2;
        int dp[n][n];
        memset(dp, 0, sizeof(dp));

        // i，j遍历顺序根据dpTable决定，可以选择斜着或者自下往上遍历，此处为i自下往上，j自左往右遍历
        // 遍历顺序需要看base case和ans的位置决定
        for (int i = n; i >= 0; i--) {
            for (int j = i + 1; j < n; j++) {
                for (int k = i + 1; k < j; k++)
                    // 状态转移关注最后一个戳破的气球是k, 则其相邻气球为i和j
                    dp[i][j] = max(dp[i][j], dp[i][k] + dp[k][j] + points[i] * points[k] * points[j]);
            }
        }

        return dp[0][n - 1];
    }
};
